home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2442 < prev    next >
Encoding:
Text File  |  1996-08-05  |  4.0 KB  |  116 lines
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: I/O Question
  5. Date: 21 Jan 1996 07:45:11 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4dtn27INNn43@keats.ugrad.cs.ubc.ca>
  8. References: <4dp1nm$mu6@taco.cc.ncsu.edu>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4dp1nm$mu6@taco.cc.ncsu.edu>, Alex David Groce  <adgroce> wrote:
  12. >I'm relatively inexperienced in C, was started with C++ here at NC State.
  13. >Anyway, working on a project where speed really matters, I'm reading
  14. >from a file containing 100001 integers in text format.  I was originally
  15. >using C++'s iostreams, but discovered the using stdio.h speeded things up
  16. >by an incredible factor.  I guess the C++ routines are so general that
  17. >they're slllooooooooww as molasses.  Anyway, I'm using scanf now, as in
  18. >
  19. >while (scanf("%i", &list[count++]) != EOF); // Read elements.
  20. >count--; // Avoid good old OBOB, the Off-By-One-Bug.
  21. >
  22. >Would it be worth my time to learn buffered I/O techniques, read or
  23. >getchar or such, to input this data?  Every little bit of time
  24. >counts...  Or is there a good example somewhere of a fast way to do
  25. >this?
  26.  
  27. Try this!
  28.  
  29. %{
  30.  
  31. /* Lex lexical analyzer */
  32.  
  33. #include <stdio.h>
  34. #define MAXSIZE 16384
  35.  
  36. int number;
  37.  
  38. %}
  39.  
  40. ws    [\n\t ]
  41. digit    [0-9]
  42. integer    "-"?{digit}+
  43.  
  44. %%
  45.  
  46. {ws}        { /* skip    */             }
  47. {integer}    { number = atoi(yytext); return 1;    }
  48. .        { /* skip illegal char */        }
  49. %%
  50.  
  51. main()
  52.  
  53. {
  54.     int list[MAXSIZE];
  55.     int count = 0;
  56.  
  57.     /* open a file, assign it to FILE *yyin        */
  58.     /* call yylex() to get numbers one by one    */
  59.     /* reads standard input by default        */
  60.  
  61.     while(yylex() && count < MAXSIZE) {
  62.         /* 'number' contains number that was read from yyin    */
  63.         list[count++] = number;
  64.     }
  65. }
  66.  
  67.  
  68.  
  69. Pump the above through the "lex" (or better, the GNU "flex"), and the compile
  70. the generated program "lex.yy.c" and link with the -ll (or -lfl if you used
  71. flex) library.
  72.  
  73. The above will make a scanner as fast as the one done with scanf(). I built the
  74. program with flex(), and it turned out to be just a bit slower than scanf(),
  75. but with flex's -f option to build a fast scanner at the expense of memory,
  76. it works almost twice as fast.
  77.  
  78. My test was an 8MB file containing the same number repeated over and over
  79. again, created by just doing a "yes 12345678 > file" and letting it run for a
  80. few seconds. 
  81.  
  82. Here, a.out is the scanf() version, and b.out is the flex -f generated version:
  83.  
  84. turing:~/src/test$ time a.out < testfile
  85. 9.26user 0.76system 0:12.43elapsed 80%CPU (0avgtext+0avgdata 0maxresident)k
  86. 0inputs+0outputs (20major+44minor)pagefaults 0swaps
  87. turing:~/src/test$ time b.out < testfile
  88. 6.70user 0.54system 0:09.58elapsed 75%CPU (0avgtext+0avgdata 0maxresident)k
  89. 0inputs+0outputs (22major+39minor)pagefaults 0swaps
  90. turing:~/src/test$ uname -a
  91. Linux turing 1.3.42 #22 Sat Jan 13 12:22:51 PST 1996 i586
  92.  
  93. I did one "dry run" before that just to make sure that one program wasn't
  94. getting an unfair advantage due to caching.
  95.  
  96. The regular expression patterns that define the lexical analyzer are compiled
  97. into a static table by lex, whereas scanf() has to parse its format string each
  98. time you call it, which is wasted overhead if the format string doesn't change
  99. from invocation to invocation.
  100.  
  101. I have written many scanners using lex, so I can write dinky things like the
  102. above off the top of my head. There are better ways to use lex, though. You can
  103. make it more efficient by being clever with how you define the pattern matches.
  104.  
  105. In my experience, a lex-generated scanner is typically at least ten times
  106. faster than programs that use scanf() as soon as your scanning starts to become
  107. non-trivial. Hand-written code based on the standard IO functions becomes hard
  108. to debug and maintain compared to a lex spec (though the latter has its own
  109. unique challenges). It's very good for doing things like: writing parsers for
  110. configuration files, importing databases from text files, scanning logs,
  111. writing lexical analyzers for compilers, text filters and the like.
  112. One thing is for sure, though: lex-generated code is bigger than a library
  113. call!
  114. -- 
  115.  
  116.